﻿// 0930train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <numeric>
#include <iomanip>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <bitset>

using namespace std;

/*
 新来的老师给班里的同学排一个队。每个学生有一个影力值。一些学生是刺头，不会听老师的话，自己选位置，非刺头同学在剩下的位置按照能力值从小到大排。对于非刺头同学，如果发现他前面有能力值比自己高的同学，他不满程度就增加，增加的数量等于前面能力值比他大的同学的个数刺头不会产生不满如果整个班级累计的不满程度超过k，那么老师就没有办法教这个班级了。

输入描述
输入有三行：
第一行为n,m,k,空格隔开，分别表示班级总人数，刺头人数，最大不满程度k。
第二行为刺头所在位置(从0开始，即排队数组的下标，比如1代表队伍中第2个同学是刺头)，位置的数组也是排序的。
第三行有n个数，空格隔开，表示老师排好的队中每人人的能力值，其中非刺头同学一定按照能力值从小到大排好序的

输出描述
0 表示老师可以继续教这个班级
1 表示老师无法继续教这个班级

说明：
n 范围是[1,10000]
m 范围是[1,n]
k 范围是[1,1000000000]
每位同学的能力值范围是[1000,100000]

示例1：
输入
4 2 3
0 1
1810 1809 1801 1802
输出
1
说明
刺头在0,1位置，2号同学不满程度2(前面两人刺头能力值都比他大)，3号同学不满程度2，总不满程度4，大于3。输出不能教这班 (1)。
请结合示例1，逐行解释下这些代码

示例2：
输入
4 2 4
0 1
1810 1809 1801 1802
输出
0
班级总人数，刺头人数，最大不满程度k

6 3 4
0 1 3
1810 1809 1801 2025 1802 1900
 */
class Solution01
{
public:
    int checkBackIndex(int confuse_i)
    {
        //二分查找normal_index_v第一个大于confuse_i的元素
        int normal_size = normal_index_v.size();
        int left = 0, right = normal_size;
        int result = -1;
        while (left<right)
        {
            int mid = left + (right - left) / 2;
            if (normal_index_v[mid]>confuse_i)
            {
                //偏大，缩小范围
                result = normal_index_v[mid];
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
            //while---
        }
        return result;
        //checkBackIndex
    }
    int checkBigger(int confuse_num)
    {
        //二分查找normal_num_v第一个大于confuse_num的元素
        int normal_size = normal_num_v.size();
        int left = 0, right = normal_size;
        int result = -1; //保存坐标
        while (left<right)
        {
            int mid = left + (right - left) / 2;
            if (normal_num_v[mid].first>confuse_num)
            {
                result = normal_num_v[mid].second;
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }
        return result;
	    //checkBigger
    }

    Solution01(int total, vector<int>&confuse_v, vector<int>&num_vec, int limit)
    {
        total_ = total;
        for (auto&index:confuse_v)
        {
            confuse_set.insert(index);
        }

        for (int i=0; i<total; i++)
        {
	        if (confuse_set.count(i)==0)
	        {
                normal_num_v.push_back(make_pair(num_vec[i], i));
                normal_index_v.push_back(i);
	        }
        }

        int result = 0;
        for (auto& confuse_i : confuse_v)
        {
            int back_i = checkBackIndex(confuse_i);
            if (back_i == -1)
            {
	            //说明confuse后面没有元素，不可能增大
                continue;
            }
            int bigger_i = checkBigger(num_vec[confuse_i]);
            if (bigger_i==-1)
            {
	            //说明整个normal数组，没有一个比confuse大
                int normal_size = normal_index_v.size();
                result += normal_size;
                continue;
            }
            result += bigger_i - back_i;
        }

        if (result>limit)
        {
            cout << 1;
            return;
        }
        cout << 0;
	    //Solution01
    }
private:
    int total_ = 0;
    vector<pair<int,int>>normal_num_v;
    vector<int>normal_index_v;
    unordered_set<int>confuse_set;
};

class Solution11
{
public:
    int checkBackIndex(int confuse_i)
    {
        //二分查找normal_index_v第一个大于confuse_i的元素
        int normal_size = normal_index_v.size();
        int left = 0, right = normal_size;
        int result = -1;
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (normal_index_v[mid] > confuse_i)
            {
                //偏大，缩小范围
                result = mid;
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
            //while---
        }
        return result;
        //checkBackIndex
    }
    int checkBigger(int confuse_num)
    {
        //二分查找normal_num_v第一个大于confuse_num的元素
        int normal_size = normal_num_v.size();
        int left = 0, right = normal_size;
        int result = -1; //保存坐标
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (normal_num_v[mid] > confuse_num)
            {
                result = mid;
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }
        return result;
        //checkBigger
    }

    Solution11(int total, vector<int>& confuse_v, vector<int>& num_vec, int limit)
    {
        total_ = total;
        for (auto& index : confuse_v)
        {
            confuse_set.insert(index);
        }

        for (int i = 0; i < total; i++)
        {
            if (confuse_set.count(i) == 0)
            {
                normal_num_v.push_back(num_vec[i]);
                normal_index_v.push_back(i);
            }
        }

        int result = 0;
        for (auto& confuse_i : confuse_v)
        {
            int back_i = checkBackIndex(confuse_i);
            if (back_i == -1)
            {
                //说明confuse后面没有元素，不可能增大
                continue;
            }
            int bigger_i = checkBigger(num_vec[confuse_i]);
            if (bigger_i == -1)
            {
                //说明整个normal数组，没有一个比confuse大
                //它后面的元素会增大result
                int normal_size = normal_index_v.size();
                result += (normal_size-back_i);
                continue;
            }
            result += bigger_i - back_i;
        }

        if (result > limit)
        {
            cout << 1;
            return;
        }
        cout << 0;
        //Solution01
    }
private:
    int total_ = 0;
    vector<int>normal_num_v;
    vector<int>normal_index_v;
    unordered_set<int>confuse_set;
};


/*
 给出n个牌数，在-100到100之间，求最大得分。

规则如下：连续翻牌，如果选当前牌，则总得分等于上一次翻牌总得分加上当前牌的数字，

如果当前总得分小于它前三次的总得分的话，那此次不翻牌，并且总得分就等于它前三次的得分。

1到3次翻牌数如果小于0的话就取0。

例子：1，-5，-6，4，7，2，-2

说明：
（1）1大于零 翻牌
（2）-5 加上1 小于0 不翻 结果为0
（3）-6 加上0 小于0 不翻 结果为0
（4）4 加上0 大于0（1）翻牌 结果为4
（5）7 加上4 大于0（2） 翻牌 结果为11
（6）2 加上11 大于0（3） 翻牌 结果为13
（7）-2 加上14 大于4（4）翻牌 结果为11

1,-5,-6,4,7,2,-2
 */
class Solution02
{
public:
    Solution02(vector<int>&num_vec)
    {
        //前三次翻牌，不能小于0
        //第4次翻牌，2个选择：1之前总分+当前总和 2继承前3次得分index-3
        if (num_vec.empty())
        {
            cout << 0;
            return;
        }

        //dp[i]=max(num_vec[i]+dp[i-1], dp[i-3])
        int v_size = num_vec.size();
        vector<long long>dynamic_v(v_size);

        //初始化
        dynamic_v[0] = max(num_vec[0], 0);
        for (int i=1; i<=2; i++)
        {
            long long curr = num_vec[i] + dynamic_v[i-1];
            dynamic_v[i] = max(curr, 0LL);
        }

        for (int i=3; i<v_size; i++)
        {
            long long curr = num_vec[i] + dynamic_v[i-1];
            dynamic_v[i] = max(curr, dynamic_v[i - 3]);
	        //for---
        }

        cout << dynamic_v[v_size - 1];
	    //Solution02
    }
};

/*
回文串的定义：正读和反读都一样的字符串
现在已经存在一个不包含回文串的字符串，
字符串的字符都是在英语字母的前N个且字符串不包含任何长度大于等于2的回文串；
请找出下一个字典序的不包含回文串的、字符都是在英语字母的前N个、且长度相同的字符串。
如果不存在，请输出NO。

输入描述
输入包括两行。
第一行有一个整数N（1<=N<=26），表示字符串的每个字符范围都是前N的英语字母。
第二行输入一个字符串（输入长度<=10000），输入保证这个字符串是合法的并且没有包含回文串。

输出描述
输出下一个字典序的不包含回文串的、字符都是在英语字母的前N个、且长度相同的字符串；
如果不存在,请输出"NO"。

示例1 输入输出示例仅供调试，后台判题数据一般不包含示例
输入
3
cba
输出
NO

示例2 输入输出示例仅供调试，后台判题数据一般不包含示例
输入
4
abcd
输出
abda

下一个字典序的
英语字母的前N个字符，不包含任何长度大于等于2的回文串
 */
class Solution03
{
public:
    bool checkPalindrome(vector<char>& char_vec)
    {
        vector<char>check_vec;
        for (auto&ch:char_vec)
        {
            //去除待赋值的字符
	        if (ch!='0')
	        {
                check_vec.push_back(ch);
	        }
        }

        //相邻两个相等
        int v_size = check_vec.size();
        for (int i=1; i<v_size; i++)
        {
            if (check_vec[i] == check_vec[i - 1]) 
                return true;
            if (i - 2 >= 0 && check_vec[i] == check_vec[i - 2]) 
                return true;
        }
        return false;
        //checkPalindrome
    }
    Solution03(int N, vector<char>&char_vec)
    {
        int v_size = char_vec.size();
        int index = v_size - 1;
        while (true)
        {
            if (index == v_size)break;
            if (index<0)
            {
                cout << "NO";
                return;
            }

            if (char_vec[index]-'a'+1==N)
            {
                //如果这一位没法往上递增，那么直接为空
                //往前一位
                char_vec[index] = '0';
                index--;
                continue;
            }

            if (char_vec[index]=='0')
            {
                char_vec[index] = 'a';
            }
        	else
            {
                int add = char_vec[index] - 'a' + 1;
                char_vec[index] = 'a' + add;
            }
            
            if (!checkPalindrome(char_vec))
            {
                index++;
            }
            //while---
        }

        string result;
        for (auto&ch:char_vec)
        {
            result += ch;
        }
        cout << result;
	    //Solution03
    }
};


/*
 给定一个二维数组M行N列，二维数组里的数字代表图片的像素，为了简化问题，
 仅包含像素1和5两种像素，每种像素代表一个物体，2个物体相邻的格子为边界，
 求像素1代表的物体的边界个数。
像素1代表的物体的边界指与像素5相邻的像素1的格子，
边界相邻的属于同一个边界，
相邻需要考虑8个方向(上，下，左，右，左上，左下，右上，右下)

输入描述
第一行，行数M，列数N
第二行开始，是M行N列的像素的二维数组，仅包含像素1和5

输出描述
像素1代表的物体的边界个数。如果没有边界输出0（比如只存在像素1，或者只存在像素5）

输入
6 6
1 1 1 1 1 1
1 5 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 5
输出
2

示例2 输入输出示例仅供调试，后台判题数据一般不包含示例
输入
6 6
1 1 1 1 1 1
1 5 5 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 5 1
1 1 1 1 1 1
输出
1
 */
class Solution04
{
public:
    void initGrid(vector<vector<int>>& grid)
    {
        for (int r=0; r<row_size_;r++)
        {
	        for (int c=0; c<col_size_; c++)
	        {
                if (grid[r][c] != 5) continue;

                for (auto&dir_v:DirectionGrid)
                {
                    int row = r + dir_v[0];
                    int col = c + dir_v[1];

                    bool is_row = row >= 0 && row < row_size_;
                    bool is_col = col >= 0 && col < col_size_;

                    if (!is_row || !is_col) continue;

                    bool is_available = grid[row][col] == 1;
                    if (is_available) grid[row][col] = 3;

                    //for
                }

                //for---
	        }
            //for--
        }

	    //initGrid
    }

    void bfs(
        vector<vector<int>>& grid,
        vector<vector<bool>>&checked,
        deque<vector<int>>&bfs_queue
    )
    {
        while (!bfs_queue.empty())
        {
            vector<int>top_node = bfs_queue.front();
            bfs_queue.pop_front();

            for (auto&dir_v:DirectionGrid)
            {
                int row = top_node[0] + dir_v[0];
                int col = top_node[1] + dir_v[1];

                bool is_row = row >= 0 && row < row_size_;
                bool is_col = col >= 0 && col < col_size_;

                if (!is_row || !is_col) continue;
                bool is_visited = checked[row][col];
                bool is_available = grid[row][col] == 3;

                if (!is_visited && is_available)
                {
                    bfs_queue.push_back({ row,col });
                    //标为已访问
                    checked[row][col] = true;
                }

	            //for
            }

            //while---
        }

	    //bfs
    }

    Solution04(vector<vector<int>>&grid, int row_size, int col_size)
    {
        row_size_ = row_size;
        col_size_ = col_size;

        initGrid(grid);
        vector<vector<bool>>checked(row_size_, vector<bool>(col_size_,false));
        deque<vector<int>>bfs_queue;

    	int result = 0;
        for (int r=0; r<row_size; r++)
        {
	        for (int c=0; c<col_size; c++)
	        {
                if (grid[r][c]==3 && !checked[r][c])
                {
                    bfs_queue.push_back({ r,c });
                    //标为已访问
                    checked[r][c] = true;
                    bfs(grid, checked, bfs_queue);
                    result += 1;
                }

		        //for---
	        }
            //for---
        }
        cout << result;
	    //Solution04
    }
private:
    int row_size_ = 0, col_size_ = 0;
    unordered_set<string>pos_cache;
    vector<vector<int>>DirectionGrid = {
        {-1,0},{1,0},{0,-1},{0,1},
		{-1,-1},{-1,1},{1,-1},{1,1}
    };
};



int main()
{
	{
  //      string binary = "1011";
		//bitset<32>bs(binary);
  //      uint64_t num = bs.to_ulong();

        int row_size, col_size;
        cin >> row_size >> col_size;

        vector<vector<int>>grid(row_size, vector<int>(col_size));
        for (int r=0; r<row_size; r++)
        {
	        for (int c=0; c<col_size; c++)
	        {
                cin >> grid[r][c];
	        }
        }

        Solution04 solu(grid, row_size, col_size);

        return 0;
	}
	{
/*
3
cba
*/
        int N;
        cin >> N;
        string str;
        cin >> str;

        vector<char>char_vec;
        for (auto&ch:str)
        {
            char_vec.push_back(ch);
        }

        Solution03 solu(N, char_vec);


        return 0;
	}
	{
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        vector<int>num_vec;
        while (getline(oh_sstream, token, ','))
        {
            num_vec.push_back(stoi(token));
        }
        Solution02 solu(num_vec);

        return 0;
	}
    //n,m,k 总人数，刺头人数，最大不满程度k
    int total, confuse_size, limit;
    cin >> total >> confuse_size >> limit;

    vector<int>confuse_v(confuse_size);
    for (int i=0; i<confuse_size; i++)
    {
        cin >> confuse_v[i];
    }

    vector<int>num_vec(total);
    for (int i=0; i<total; i++)
    {
        cin >> num_vec[i];
    }

    Solution11 solu(total, confuse_v, num_vec, limit);


}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
